1. Field of the Invention
The present invention relates to a method and apparatus for encoding an image based on image communication and an image data base.
2. Description of the Related Art
In a facsimile apparatus (as a typical example of a conventional still image communication apparatus), an image is sequentially scanned in a raster direction, and the scanned data is encoded and transmitted. According to this scheme, in order to obtain the entire image, encoded data of the entire image must be transmitted, which results in a long transmission time. It is therefore difficult to apply this scheme to image data base services and image communication service such as video telex service.
In order to acquire and handle the entire image at high speed, hierarchical encoding can be proposed. FIG. 1 shows a conventional hierarchical encoding scheme. An image is reduced to 1/2 by subsampling in both main scanning and subscanning directions to obtain a 1/2-reduced image. The 1/2-reduced image is further reduced to obtain a 1/4-reduced image. This operation is repeated to obtain sequentially lower-resolution images. Encoding is started from these low-resolution images, and the encoded images are sequentially transmitted, thereby allowing acquisition of the entire image at the receiving side at high speed. In the example of FIG. 1, an image is reduced to 1/2, 1/4, and 1/8 in both the main scanning and subscanning directions, and encoding is performed in the order 1/8, 1/4, 1/2, and 1 (one-to-one size image or original image). The encoded data are then transmitted also in the above order.
Referring to FIG. 1, frame memories (FM1, FM1/2, FM1/4, and FM1/8) 101 to 104 store an original image, and 1/2-1/4- and 1/8-reduced images, respectively.
Reduction units (RDs) 105 to 107 generate 1/2-1/4- and 1/8-reduced images. Encoders 108 to 111 encode the 1/8-1/4- and 1/2-reduced images and the original image, respectively. In encoding the 1/8-reduced image, the 1/8-reduced images stored in the frame memory 104 are sequentially scanned, and entropy coding such as arithmetic encoding is performed with reference to a noticed pixel (i.e., the pixel current in question) and neighboring pixels. For the 1/4reduced image, encoding efficiency can be increased by referring to the neighboring pixels of the noticed pixel and the neighboring pixels of the 1/8-reduced image. Similarly, the 1/2-reduced image is encoded with reference to the 1/4-reduced image, and the original image is encoded with reference to the 1/2-reduced image.
As is apparent from the prior art shown in FIG. 1, reduction is performed in the order 1/2, 1/4, and 1/8. Encoding is performed in the order 1/8, 1/4, 1/2, and 1, from the lower-resolution images. One frame memory is required for an image of each stage (reduction size). The number of reduction circuits must be the number of stages of the images.
In the prior art, therefore, the capacity of a memory for storing images of the respective stages is inevitably increased, and the reduction units for generating reduced images are required in units of stages, thus resulting in a bulky apparatus.
Conventional image encoding schemes include the MH scheme for encoding continuity (i.e., run length) of a monochromatic image, the MR scheme, and the MMR scheme. When a halftone image obtained by a dither method or an error diffusion method is encoded by using such an encoding scheme, the data volume of the encoded image is larger than that of the original image since the halftone image has short run lengths.
In recent years, an arithmetic encoding scheme (G. G. Langdon and J. J. Rissanen, "Compression of Black-White Images with Arithmetic Coding", IEEE Trans. Commun. COM-29, 1981) has received a great deal of attention. This scheme is known as a highly efficient encoding scheme whose encoding efficiency is determined by probability of occurrence, regardless of run lengths, of white and black runs.
In a conventionally known arithmetic encoding scheme, however, a probability of occurrence of minor symbols in an image to be encoded is required during encoding. For example, an image to be encoded is prescanned to obtain statistical data, and a probability of occurrence of minor symbols must be calculated in correspondence with each image.
In a conventional dynamic arithmetic encoding scheme which does not require prescanning, images to be input are sequentially monitored to obtain minor symbols. According to this scheme, however, a predetermined number of pixels are referred to regardless of the size of an image to be encoded. When the image is small, encoding efficiency is undesirably decreased.
More specifically, when the number of reference pixels is large for an image of a small size, the possibility of occurrence of each state is decreased. As a result, encoding is completed before an initial value is converged to an optimal value, thus degrading the encoding efficiency.